#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTEX_NUM 100

typedef struct
{
    int vertexNum;                             // 顶点数
    int edgeNum;                               // 边数
    int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
} Graph;

bool visited[MAX_VERTEX_NUM]; // 访问标记数组

typedef struct
{
    int data[MAX_VERTEX_NUM];
    int front, rear;
} Queue;

Queue Q;

// 队列操作
void InitQueue(Queue *Q)
{
    Q->front = Q->rear = 0;
}

bool isEmpty(Queue *Q)
{
    return Q->front == Q->rear;
}

void EnQueue(Queue *Q, int x)
{
    Q->data[Q->rear++] = x;
}

void DeQueue(Queue *Q, int *x)
{
    *x = Q->data[Q->front++];
}

// 简单的访问函数
void visit(int v)
{
    printf("访问节点：%d\n", v);
}

// 找第一个邻接点
int FirstNeighbor(Graph G, int v)
{
    for (int i = 0; i < G.vertexNum; i++)
    {
        if (G.edges[v][i] == 1)
            return i;
    }
    return -1;
}

// 找下一个邻接点
int NextNeighbor(Graph G, int v, int w)
{
    for (int i = w + 1; i < G.vertexNum; i++)
    {
        if (G.edges[v][i] == 1)
            return i;
    }
    return -1;
}

// BFS 单次广度优先遍历
void BFS(Graph G, int v)
{
    visit(v);
    visited[v] = true;
    EnQueue(&Q, v);

    while (!isEmpty(&Q))
    {
        int u;
        DeQueue(&Q, &u);
        for (int w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w))
        {
            if (!visited[w])
            {
                visit(w);
                visited[w] = true;
                EnQueue(&Q, w);
            }
        }
    }
}

// 遍历整个图（支持非连通图）
void BFSTraverse(Graph G)
{
    for (int i = 0; i < G.vertexNum; ++i)
        visited[i] = false; // 初始化访问标记

    InitQueue(&Q); // 初始化队列

    for (int i = 0; i < G.vertexNum; ++i)
    {
        if (!visited[i])
            BFS(G, i); // 从每个未访问过的顶点开始 BFS
    }
}

// 示例图初始化
void CreateSampleGraph(Graph *G)
{
    G->vertexNum = 5;
    G->edgeNum = 6;

    for (int i = 0; i < G->vertexNum; i++)
    {
        for (int j = 0; j < G->vertexNum; j++)
        {
            G->edges[i][j] = 0;
        }
    }

    G->edges[0][1] = G->edges[1][0] = 1;
    G->edges[0][2] = G->edges[2][0] = 1;
    G->edges[1][3] = G->edges[3][1] = 1;
    G->edges[1][4] = G->edges[4][1] = 1;
    G->edges[2][4] = G->edges[4][2] = 1;
}

int main()
{
    Graph G;
    CreateSampleGraph(&G);

    printf("广度优先遍历整个图：\n");
    BFSTraverse(G);

    return 0;
}
